#coding=utf-8
import collections
class BSTonde():
    def __init__(self,parent,t):
        self.value = t
        self.left = None
        self.right = None
        self.parent = parent


class BST():
    def __init__(self):
        self.root = None

    def insert(self,TreeNode:BSTonde,t:str) -> BSTonde:   #插入
        if t < TreeNode.value:
            if TreeNode.left is None:
                TreeNode.left = BSTonde(self,t)
                return TreeNode.left
            else:
                return self.insert(TreeNode.left,t)
        else:
            if TreeNode.right is None:
                TreeNode.right = BSTonde(self,t)
                return TreeNode.right
            else:
                return self.insert(TreeNode.right,t)

    def find_min(self,TreeNode:BSTonde) -> BSTonde:  #查找搜索树的最小值
        while TreeNode.left:
            TreeNode = TreeNode.left
        return TreeNode

    def delete(self,TreeNode:BSTonde,key:str) -> BSTonde:  #删除搜索树值为k的节点
        '''
        如果被删除的树节点同时有左右子树，
        只有左子树，
        :param TreeNode:
        :param key:
        :return:
        '''
        if not TreeNode:
            return None
        if TreeNode.value > key:
            TreeNode.left = self.delete(TreeNode.left,key)
        elif TreeNode.value < key:
            TreeNode.right = self.delete(TreeNode.right,key)
        else:
            if TreeNode.left and TreeNode.right:
                node_min = self.find_min(TreeNode.right)
                TreeNode.value = node_min.value
                TreeNode.right=self.delete(TreeNode.right,node_min.value)
            elif TreeNode.left and not TreeNode.right:
                TreeNode = TreeNode.left
            elif TreeNode.right and not TreeNode.left:
                TreeNode = TreeNode.right
            else:
                TreeNode = None
        return TreeNode

    def POT(self,TreeNode:BSTonde) -> list: #后序遍历
        if not TreeNode:
            return []
        left = self.POT(TreeNode.left)
        right = self.POT(TreeNode.right)
        return left + right + [TreeNode.value]




# BstTree = BST()
# BstTree.root = BSTonde(None,'E')
# strlist = ['A','S','Y','Q','U','E','S','T','I','O','N']
# for i in range(len(strlist)):
#     BstTree.insert(BstTree.root,strlist[i])
# print("搜索二叉树的后序遍历结果为： " , end="")
# print(BstTree.POT(BstTree.root))
# print("该搜索二叉树的最小结点值为： ",end="")
# print(BstTree.find_min(BstTree.root).value)
#
# print("请输入删除的节点的值： ", end="")
# del_val = input()
# BstTree.delete(BstTree.root,del_val)
# print("删除后搜索二叉树的后序遍历结果为： ",end="")
# print(BstTree.POT(BstTree.root))


import collections


class BiTreeNode:
    def __init__(self, t, left=None, right=None):
        self.value = t
        self.left = left
        self.right = right


class BiTree:
    def __init__(self):
        self.root = None

    def isComplete(self) -> bool:  # BFS判断是否为完全二叉树
        if not self.root:
            return False
        temp = collections.deque()
        temp.append(self.root)
        flag = False
        while temp:
            treenode = temp.popleft()
            if treenode.left:
                temp.append(treenode.left)
            if treenode.right:
                temp.append(treenode.right)
            if treenode.right and (not treenode.left):
                return False
            if flag:
                if treenode.left or treenode.right:
                    return False
            if (not treenode.left) and (not treenode.right):
                flag = True
            if treenode.left and (not treenode.right):
                flag = True
        return True

    def hasValueProperty(self) -> bool:  # BFS判断二叉树是否满足堆性质
        if not self.root:
            return False
        temp = collections.deque()
        temp.append(self.root)
        while temp:
            treenode = temp.popleft()
            if treenode.left:
                temp.append(treenode.left)
                if treenode.left.value > treenode.value:
                    return False
            if treenode.right:
                temp.append(treenode.right)
                if treenode.right.value > treenode.value:
                    return False
        return True


# tree1 = BiTree()
# tree1.root = BiTreeNode('F', left=BiTreeNode('E', left=BiTreeNode('D'), right=BiTreeNode('C')),
#                         right=BiTreeNode('B', left=BiTreeNode('A')))
# tree1str = '''
# tree1的形状为                       F
#                                 /   \\
#                                E     B
#                               / \\   /
#                              D   C  A
# '''
# print(tree1str)
# print("判断是否为完全二叉树: " + str(tree1.isComplete()))
# print("判断二叉树是否满足堆性质: " + str(tree1.hasValueProperty()))
# print()
# tree2 = BiTree()
# tree2.root = BiTreeNode('F', left=BiTreeNode('E', left=BiTreeNode('D')),
#                         right=BiTreeNode('C', left=BiTreeNode('A'), right=BiTreeNode('B')))
# tree2str = '''
# tree2的形状为                       F
#                                 /   \\
#                                E     C
#                               /     / \\
#                              D     A   B
# '''
# print(tree2str)
# print("判断是否为完全二叉树: " + str(tree2.isComplete()))
# print("判断二叉树是否满足堆性质: " + str(tree2.hasValueProperty()))


#堆
class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def buildHeap(self,alist:list)->None:
        mid = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList += alist[:]
        while(mid>0):
            self.max_heapify_rec(mid)
            mid -= 1

    def max_heapify_rec(self,i:int)->None:
        if(i * 2) <= self.currentSize:
            mc = self.maxChild(i)
            if self.heapList[i] < self.heapList[mc]:
                self.heapList[i] , self.heapList[mc] = self.heapList[mc] , self.heapList[i]
                self.max_heapify_rec(mc)

    def maxChild(self,i):
        leftchild = i * 2
        rightchild = i * 2 + 1
        if leftchild <= self.currentSize and self.heapList[leftchild] > self.heapList[i]:
            largest = leftchild
        else:
            largest = i
        if rightchild <= self.currentSize and self.heapList[rightchild] > self.heapList[largest]:
            largest = rightchild
        return largest

    def insert(self,i):
        self.heapList.append(i)
        self.currentSize += 1

    def printlist(self):
        return self.heapList[1:]

    def heapsort(self):
        '''
        每次更换根节点时，将堆中最后一个元素插入到根结点位置，并将堆中最后一个元素弹出。
        :return:
        '''
        sortedh = []
        while self.currentSize > 0:
            sortedh.append(self.heapList[1])
            self.heapList[1] = self.heapList[self.currentSize]
            self.heapList.pop(-1)
            self.currentSize -= 1
            self.max_heapify_rec(1)
        return sortedh

def find_min_heap(A,k):
    numheap = BinHeap()
    for i in range(len(A)):
        if numheap.currentSize < k:
            numheap.insert(A[i])
            numheap.max_heapify_rec(1)
            continue
        if A[i] < numheap.heapList[1]:
            numheap.heapList[1] = A[i]
            numheap.max_heapify_rec(1)
    return numheap.printlist()

import random
N = int(input("请输入N的值： "))
numlist = [random.randint(1,1000) for i in range(N)]
print(f"初始化数组的值为: {numlist}")
k = int(input("请输入k的值： "))
print(f"其中最小的{k}个值为: {find_min_heap(numlist,k)}")